In recent years, as information society and mobile computing technology are rapidly advanced, personal digital assistants (PDA), hand-held personal computer (HPC), cellular phone, e-book and the like have been developed. In addition, for the purpose of data storage, many flash memories are widely used because they are very handy to carry and have a fast access time and a low power consumption.
A flash memory has features different from a general random access memory (RAM). The flash memory can be nonvolatile and firmer than a hard disk drive. Additionally, the flash memory can operate with low power and has an access time as fast as the RAM. Further, the flash memory is adaptable to portable devices because of its small size.
However, the flash memory is five to ten times more expensive than the hard disk drive and has a disadvantage in that a cleaning operation must be carried out in order to write a new data to a space where data has already existed.
For instance, while 28F640J3A flash memory developed by Intel Corporation has a fast read speed of 100 to 150 nsec, which is similar to the RAM, its write speed and erase speed are relatively slow. It takes 218 μsec to write data when 32-byte buffer is used, and a write time of an erase block unit is 0.8 sec per block.
In addition, an erase block size that can be erased at a time is constantly 128 Kbytes. The flash memory can perform erase/write operations 100,000 times at a room temperature. Such a space of the flash memory, which can be erased at a time, is called “erase block” or “segment”.
Flash memories can be classified into NOR type, NAND type and AND type according to cell structures. Generally, the NOR or NAND flash memory is widely used. The NOR flash memory has a fast random-access read speed and an easiness of access per bit. Therefore, the NOR flash memory is directly connected to a memory address space and mainly used to store codes executed by CPU. Meanwhile, the NAND flash memory has a relatively slow random access time, so that it is mainly used to store relatively large data, such as music files or image files, at a time.
Conventional file systems using these flash memories are disclosed in U.S. Pat. No. 5,404,485, entitled. “Flash Memory System”, and in a paper “A Flash Memory Based File System”, pp. 155-164, published at USENIX conference in 1995.
Additionally, there is provided a journaling flash file system (JFFS), in which a log-structured file system is applied to a flash memory. The log-structured file system is disclosed in U.S. Pat. No. 6,128,630 entitled “Journal space release for log-structured storage systems” and U.S. Pat. No. 5,530,850 entitled “Data storage library array with log-structured file system which allows simultaneous write and garbage collection”.
When a file system is configured in a hard disk drive and data is stored, the log-structured file system employs a journaling storing method. Accordingly, the log-structured file system has an advantage in that versions of a previous data and a new modified data can be maintained in a log format. Further, erroneous data can be restored to the previous data.
The JFFS was developed by Axis Communications of U.S.A, and JFFS2 has been developed under GNU public licenses (GPL) of free software foundation (FSF) by RedHat of U.S.A.
FIG. 1 is an exemplary view of a storing method of JFFS2 which configures a file system of a flash memory.
In FIG. 1, there is shown one example of storing data into the flash memory in the JFFS. In case there is a directory structure in a certain file system, for example, EXT2 of Linux, a directory entry (Dir 1 entry) is stored in order to contain a general characteristic of one directory, as shown in FIG. 1(a). Here, the stored information is a directory node type, a total length of node, a cyclic redundancy check (CRC) of head, parent inode number, version value, node CRC, name CRC, directory name, etc.
As shown in FIG. 1, a directory inode (Dir 1 inode) is stored after the directory entry (Dir 1 entry). The information stored in the directory inode (Dir 1 inode) includes a node type, a total length, various kinds of CRC, version value, user ID, group ID, created time, accessed time, modified time, etc.
The directory entry and the directory inode are additional information used only in the file system, not information that is visible to the user. They are called “meta data”. In the same manner, when a file contained in the directory is stored, a file entry (File 1 entry) and a file inode (File 1 inode) are stored sequentially.
The directory and the file are considered as the same format in the file system. However, while there is no actual data in the directory, a file data (File 1 data) is stored after the file inode (File 1 node).
In this manner, the JFFS employs a method for journaling the directory and file of the flash memory. As shown in FIG. 1(b), if the directory inode (Dir 1 inode) and the file inode (File 1 inode) are changed and updated with new values, the original meta data are changed into an invalid state and new data are sequentially stored in storage locations.
At this time, the invalid state is only to indicate that the data are an unnecessary data, not to actually erase the data. Version values of the new data increase by one stage. Therefore, if a problem occurs in the new data, data can be easily restored only if there are the data of the previous version.
In this manner, if the directory and the file are updated and new data are stored many times, the storage space of the flash memory reaches the limit. Thus, data stored in the flash memory must be erased in order to secure the storage space. Since the data must be erased only by the erase block unit due to the characteristic of the flash memory, the valid data (Dir 1 entry) moves as shown in FIG. 1(c). Then, if the erase block is filled with invalid spaces, the cleaning operation is carried out to erase one erase block, as shown in FIG. 1(d).
The above process of securing the new storage space is called “garbage collection (GC)” In other words, when it is necessary to secure the new storage space for lack of the storage space, the garbage collection is carried out by collecting the invalid spaces and cleaning the erase block by the erase block unit. In addition, the space where the new data created through the cleaning operation can be stored is called “free space”. By securing large free space, data can continue to be stored.
In case the hard disk drive is used as the storage medium, data can be stored in the similar manner. In case of the hard disk drive, however, the invalid data does not move and the invalid block having the erase block size is not created in order to secure the storage space.
However, in order to obtain the fast access to the file in the hard disk drive, several pieces of the same file are collected and moved to a physically adjacent location. Since the hard disk drive need not perform the cleaning operation separately, the data are directly stored if the space where the new data are stored is in the invalid state.
If the storing method of the JFFS is carried out, the locations of the entry and the inode are mixed complicatedly with the data of the file. Therefore, when the file system is configured by connecting and mounting the flash memory and an operating system (OS), the entire space of the flash memory must be read out and the metal data must be found in order to configure the tree-type directory structure.
The same problem also occurs when a log-structured file system or a journaling file system is configured using the hard disk drive as the storage medium, instead of the flash memory. In other words, although the data need not move in order to collect the erase block like the case of the flash memory, the access speed becomes 40-50 times slower than the flash memory because the meta data are mixed with the data of the file and scattered throughout the space. In addition, it takes much time to configure the file system by reading out the entire disk whose capacity can be more than gigabytes.
The hard disk drive mainly uses the log-structured file system or the journaling file system to store and reproduce a large-size multimedia data. However, the utility as the multimedia file system is degraded if the data is not transmitted at a constant speed per predetermined time due to the mixture of the meta data.